#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

 

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：

输入：amount = 10, coins = [10]
输出：1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/coin-change-2
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//很明显 这个可以感觉到是完全背包问题
//TODO 有错误 很明显自己理解没那么透彻 1 for 循环不清楚 2 dp 公式不清楚 因为这个求的是个数而不是value  3 return dp[]最后这个返回不清楚
//我擦可以说都特么不清楚
int change(int amount, vector<int> &coins) {

    vector<int> dp(amount + 1, 0);


    dp[0] = 1;
    //循环外层coin 先物品 后背包
    for (int i = 0; i < coins.size(); ++i) {

        for (int j = 0; (amount + 1) > j; ++j) {
            //这个求的是次数3
            if (j - coins[i] >= 0)
                dp[j] += dp[j - coins[i]];
            // dp[j] = max(dp[j], dp[j - coins[i]] + coins[i]);
        }


    }


    return dp[amount];

}
//如果 这里交换 i j 遍历顺序求出来的就是 全排列的数量 而不是组合的数量
//在求装满背包有⼏种⽅案的时候，认清遍历顺序是⾮常关键的。
//如果求组合数就是外层for循环遍历物品，内层for遍历背包。
//如果求排列数就是外层for遍历背包，内层for循环遍历物品
